講義概要/Class Outline

本講義では数学的かつ抽象的な計算モデルを用いて、計算機（コンピュータ）による計算あるいは処理とはいかなるものかについて理論的に学ぶ。具体的には、まず、最も基礎的な計算モデルである決定性有限オートマトンを取り上げ、遷移表と遷移図、数学的定義を用いて決定性有限オートマトンの動作を理解する。また、決定性有限オートマトンを拡張した計算モデルである、非決定性有限オートマトンについても学習し、その動作の理解に努める。また、決定性有限オートマトンと非決定性有限オートマトンの計算能力を比較する。なお、しっかりと理解するためには自分自身の手による問題演習が欠かせないので、演習を行いながら講義を進める。
 

講義計画 /Class Structure

回	内容
1	講義概要 講義概要と計画について説明する。
2	決定性有限オートマトンの動作 抽象的な計算モデルである決定性有限オートマトンの動作について解説する。
3	決定性有限オートマトンとプログラム 決定性有限オートマトンとプログラムの動作についての関係について解説する。
4	遷移表と遷移図 決定性有限オートマトンの動作を記述する遷移表と遷移図について解説する。
5	決定性有限オートマトンの数学的定義（１） 決定性有限オートマトンの数学的定義について解説する。
6	決定性有限オートマトンの数学的定義（２） 決定性有限オートマトンの数学的定義と遷移表・遷移図との関連ならびに、決定性有限オートマトンの動作に関わる諸定義を解説する。
7	小テスト１ 第６回までの内容についてテストを行う。
8	補足と復習 小テストの解説ならびに、補足と復習を行う。
9	決定性有限オートマトンと言語 決定性有限オートマトンが受理する言語の概念と、一般的な問題(処理内容)との関連について解説する。
10	非決定性有限オートマトン 非決定性有限オートマトンの動作、遷移表、遷移図、数学的定義について解説する。
11	非決定性有限オートマトンと言語 非決定性有限オートマトンが受理する言語の概念について解説する。
12	決定性有限オートマトンと非決定性有限オートマトンの計算能力 決定性有限オートマトンと非決定性有限オートマトンの計算能力について比較する。
13	小テスト２ 第８回から第１２回の内容についてテストを行う。
14	補足と復習 小テストの解説ならびに、補足と復習を行う。